package leetcode208

// ascii 码  0 < 字符 - 'a' <26
type Trie struct {
	list  [26]*Trie
	isEnd bool
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	cur := this
	for _, b := range word {
		if cur.list[b-'a'] == nil {
			cur.list[b-'a'] = new(Trie)
		}
		cur = cur.list[b-'a']
	}
	cur.isEnd = true
	return
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	for _, b := range word {
		if this.list[b-'a'] == nil {
			return false
		}
		this = this.list[b-'a']
	}
	return this.isEnd
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	for _, b := range prefix {
		if this.list[b-'a'] == nil {
			return false
		}
		this = this.list[b-'a']
	}
	return true
}
